package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.ArrayUtils;
import com.xsherl.leetcode.utils.PrintUtils;

import java.util.ArrayList;
import java.util.List;

public class InsertInterval {

    /**
     * 用新的数组存放结果
     *  1. 如果原区间小于新的区间，直接放到数组中
     *  2. 如果区间发生重叠，一直合并区间到无法合并为止，加入合并后的区间到数组
     *  3. 如果没有发生重叠，并且新区间小于原区间，将剩下的所有区间存放到数组中
     *
     * @return 需要确保列表中的区间仍然有序且不重叠
     */
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int len = intervals.length;
        List<int[]> res = new ArrayList<>();
        int newLeft = newInterval[0];
        int newRight = newInterval[1];
        int i = 0;
        boolean merged = false;
        while (i < len){
            if (newRight < intervals[i][0]){
                break;
            } else if (newLeft > intervals[i][1]){
                res.add(intervals[i]);
                ++i;
            } else {
                int l = Math.min(newLeft, intervals[i][0]);
                int r = Math.max(newRight, intervals[i][1]);
                i++;
                while (i < len && r >= intervals[i][0] && l <= intervals[i][1]) {
                    l = Math.min(l, intervals[i][0]);
                    r = Math.max(r, intervals[i][1]);
                    i++;
                }
                res.add(new int[]{l, r});
                merged = true;
                break;
            }
        }
        if (!merged){
            res.add(newInterval);
        }
        while (i < len){
            res.add(intervals[i++]);
        }
        return res.toArray(new int[0][0]);
    }

    public static void main(String[] args) {
        int[][] intervals = ArrayUtils.parseArray("" +
                "[[1,2], [9, 10]]" +
                "", int[].class);
        int[] newInterval = {4, 8};
        int[][] insert = new InsertInterval().insert(intervals, newInterval);
        PrintUtils.println(insert);
    }
}
